A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data input to the device or in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory search on a RAM, the user supplies the address and gets back the data stored in that address (location).
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address, or the data can be written into a first empty memory location (also known as the Next Free Address or NFA). Once information is stored in a memory location, it is found doing a memory search by comparing every bit in any memory location with every bit of data in a comparand register circuit. When the content stored in the CAM memory location does not match the data placed in the comparand register, the local match detect circuit associated with the CAM memory location returns a no-match indication. When the content stored in the CAM memory location matches the data placed in the comparand register, the local match detect circuit associated with the CAM memory location returns a match indication. If one or more of the local match detect circuits return a match indication then the CAM device outputs a match indication. If no local match detect circuits return a match indication then the CAM device outputs a no-match indication. In addition, if a match is found then the CAM returns the identification of the address location in which the matching data is stored (or one of the address locations in which matching data was stored if more than one memory location contained matching data). Thus, with a CAM, the user supplies the data and gets back an indication of an address where a matching data is stored in the memory.
CAMs are typically used in data network communication, wherein the CAM stores the database of clients on the network, and provides the means for search of clients addresses. Since clients come on line and then go off line, keeping all the addresses of all the clients, all the time in the database, is very wasteful. For this reason, various method are employed in deciding what data should always be kept in the database, and what data could be removed from the database, and at what time. One such method is based on the age of each entry in the database. For aging purposes, every CAM word includes a number of bits dedicated as time stamp bits. When new data is stored in the CAM, a code representing the time of the storage operation is written into the dedicated time stamp bits. Then every time data in a word matches the data in the comparand register, a match flag is activated, and the location of the matching data is provided. This operation is immediately followed by a write operation wherein the time stamp bits of the matching CAM word are loaded with a code representing the current time. Every so often, a search is conducted on the time stamp bits in the entire CAM to detect and purge CAM words which have not been matched for some time. This method though very popular does not take into account how frequently a CAM word is matched, indicating activity at that client. Consequently, a CAM device which utilizes information incorporating frequency of word matches is desired.